package org.leetcode.medium;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 四数之和
public class TestFourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int a = 0; a < nums.length; a++) {
            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }
            if ((long) nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) {
                break;
            }
            if((long)nums[a] + nums[nums.length -1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
                continue;
            }
            for (int d = nums.length - 1; d > a; d--) {
                if (d < nums.length - 1 && nums[d] == nums[d + 1]) {
                    continue;
                }
                int b = a + 1;
                int c = d - 1;

                while (b < c) {

                    if (b > a + 1 && nums[b] == nums[b - 1]) {
                        b++;
                        continue;
                    }
                    while (nums[a] + nums[b] + nums[c] + nums[d] != target && b + 1 < c) {
                        c--;
                    }
                    long sum = (long)nums[a] + nums[b] + nums[c] + nums[d];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[a]);
                        list.add(nums[b]);
                        list.add(nums[c]);
                        list.add(nums[d]);
                        if(!result.contains(list)){
                            result.add(list);
                        }
                    }
                    c = d - 1;
                    b++;
                }
            }
        }
        return result;
    }

    @Test
    public  void test() {
        TestFourSum testFourSum = new TestFourSum();
        int[] nums = {1000000000,1000000000,1000000000,1000000000};
        int target = -294967296;
        System.out.println(testFourSum.fourSum(nums, target));
    }
}
